# -*- coding:utf-8 -*-
'''
在一个nxm矩阵形状的城市里爆发了洪水，洪水从(0,0)的格子流到这个城市，在这个矩阵中有的格子有一些建筑，洪水只能在没有建筑的格子流动。请返回洪水流到(n - 1,m - 1)的最早时间(洪水只能从一个格子流到其相邻的格子且洪水单位时间能从一个格子流到相邻格子)。

给定一个矩阵map表示城市，其中map[i][j]表示坐标为(i,j)的格子，值为1代表该格子有建筑，0代表没有建筑。同时给定矩阵的大小n和m(n和m均小于等于100)，请返回流到(n - 1,m - 1)的最早时间。保证洪水一定能流到终点。
'''

class Flood:
  def floodFill(self, tmap, n, m):
    # init
    self.n = n
    self.m = m
    self.tmap = tmap
    queue = [(0, 0)]
    distance = {}
    distance[queue[0]] = 0

    # bfs
    while queue:
      point = queue.pop(0)
      for point_next in self.getNeighbors(point):
        if point_next not in distance.keys():
           distance[point_next] = distance[point] + 1
           queue.append(point_next)

    return distance[(n - 1, m - 1)]

  def getNeighbors(self, loc):
    # loc: (x, y)
    x, y = loc
    neighbor = []
    if x > 0 and self.tmap[x - 1][y] == 0:
      neighbor.append((x - 1, y))
    if x < self.n - 1 and self.tmap[x + 1][y] == 0:
      neighbor.append((x + 1, y))
    if y > 0 and self.tmap[x][y - 1] == 0:
      neighbor.append((x, y - 1))
    if y < self.m - 1 and self.tmap[x][y + 1] == 0:
      neighbor.append((x, y + 1))
    return neighbor

# test case
tmap = [
  [0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0],
  [0,1,1,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,1,0],
  [0,1,1,0,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1,1,0,1],
  [0,1,1,1,0,1,1,0,0,0,1,1,1,1,0,1,1,0,1,1,0,1,1,1,0,1,0],
  [0,1,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,0,0,1,1,1,0],
  [0,0,1,0,0,0,1,1,0,0,1,1,1,1,1,1,0,1,0,0,0,0,1,0,1,0,0],
  [0,0,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0],
  [0,1,0,1,0,0,0,0,0,1,1,0,0,1,0,1,1,0,1,1,1,1,1,1,0,0,0],
  [0,0,0,0,1,0,0,1,0,1,1,0,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1],
  [0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,0],
  [0,1,0,0,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,0,1,1,0,0,0,1,1],
  [0,0,0,0,0,0,1,1,1,1,0,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,1],
  [0,0,1,1,0,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,0,0,0,1,1,0],
  [0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,0],
  [0,1,0,0,1,1,0,1,0,1,0,1,0,0,1,1,0,0,1,1,0,1,0,1,0,0,1],
  [0,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1],
  [0,0,1,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,0,1,0],
  [0,1,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,1,0,1,1,0,0,0],
  [0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1,0,0,1,1,0,1,1,1,1,0,0],
  [0,0,0,0,1,0,0,1,1,0,1,1,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1],
  [0,1,0,0,1,0,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,1,1,1],
  [0,0,1,1,1,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0],
  [0,1,1,0,1,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,1,1,0,0,1,0,1],
  [0,0,1,1,1,0,1,1,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,1,0,1],
  [0,0,0,0,1,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0],
  [0,1,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,1,1,0,1,1,0,1],
  [0,1,1,0,0,1,1,0,0,0,0,1,0,1,1,1,1,1,0,1,0,1,1,0,0,0,1],
  [0,0,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1],
  [0,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,1,1,0,1,1,1],
  [0,0,0,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,0,0],
  [0,0,1,0,0,1,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1],
  [0,1,0,1,1,1,1,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,1],
  [0,0,0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,0,0,1],
  [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
]
n = 34
m = 27
print(Flood().floodFill(tmap, n, m) == 59)